Euler's Criterion
정수론에서 어떤 정수가 소수에 대한 이차잉여인지 아닌지를 판별하는 정리이다. 레온하르트 오일러가 1748년에 발표했으며,
르장드르 기호를 계산하는 한 방법이다.
목차
1. 진술
2. 증명
3. 예시
4. 영상
홀소수 p에 대하여 (n|p) \equiv n^{\frac{p-1}{2}} \ (\mathrm{mod}\ p)이다.
만약 (n|p)=1이라면 x^2 \equiv n\ (\mathrm{mod}\ p)인 x \in \Bbb{Z}가 존재하므로 n^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1\ (\mathrm{mod}\ p). 따라서 성립.
임의의 n \in \Bbb{Z}에 대하여 n^{\frac{p-1}{2}} \equiv \pm 1\ (\mathrm{mod}\ p)인데, 합동방정식 x^{\frac{p-1}{2}} \equiv 1\ (\mathrm{mod}\ p)의 해는 정확히 \frac{p-1}{2}개이므로 그 해는 (n|p)=1,\ 1 \leq n \leq p-1인 \frac{p-1}{2}개의 자연수들이다. 그러므로 나머지 (n|p)=-1,\ 1 \leq n \leq p-1인 \frac{p-1}{2}개의 자연수들은 n^{\frac{p-1}{2}} \equiv -1\ (\mathrm{mod}\ p)을 만족한다. 따라서 증명되었다.
(17|23) \equiv 17^{\frac{22}{2}} \equiv 17^11 \equiv 34271896307633 \equiv -1\ (\mathrm{mod}\ 23)
따라서 (17|23)=-1이다.
